package com.leetcode.algorithm.y22.m07.w4;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 841. 钥匙和房间
 * 
 * https://leetcode.cn/problems/keys-and-rooms/
 * 
 * @author jie.deng
 *
 */
class Question0841Solution02 {

	// BFS
	public boolean canVisitAllRooms(List<List<Integer>> rooms) {
		int len = rooms.size();
		boolean[] visited = new boolean[len];

		Queue<Integer> queue = new LinkedList<>();
		visited[0] = true;
		queue.offer(0);

		while (!queue.isEmpty()) {
			int roomNo = queue.poll().intValue();
			for (Integer room : rooms.get(roomNo)) {
				if (!visited[room]) {
					queue.offer(room);
					visited[room] = true;
				}
			}
		}

		for (int i = 0; i < len; i++) {
			if (!visited[i]) {
				return false;
			}
		}
		return true;
	}

}